package 动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2020-12-23
 */
public class 目标和 {
    static List<String> path = new ArrayList<>();

    //1.通过递归
    public static int solve(int[] nums, int target, int sum, int index) {
        if (index == nums.length) {
            if (target == sum) {
                System.out.println(path);
            }
            return 0;
        }
        path.add("+" + nums[index]);
        solve(nums, target, sum + nums[index], index + 1);
        path.remove(path.size() - 1);

        path.add("-" + nums[index]);
        solve(nums, target, sum - nums[index], index + 1);
        path.remove(path.size() - 1);
        return 0;
    }

    //2.通过递归
    public static int solveFor(int[] nums, int target, int sum, int index) {
        if (index == nums.length) {
            if (target == sum) {
                System.out.println(path);
            }
            return 0;
        }
        for (int j = 0; j <= 1; j++) {
            int d = 1;
            if (j == 0) {
                d *= nums[index];
                path.add("+" + nums[index]);
            } else {
                d *= -nums[index];
                path.add("-" + nums[index]);
            }
            solve(nums, target, sum + d, index + 1);
            path.remove(path.size() - 1);
        }


        return 0;
    }

    //3.通过递归累加
    public static int solveForRemember(int[] nums, int target, int sum, int index) {
        if (index == nums.length) {
            if (target == sum) {
                System.out.println(path);
                return 1;
            }
            return 0;
        }
        path.add("+" + nums[index]);
        int positive = solveForRemember(nums, target, sum + nums[index], index + 1);
        path.remove(path.size() - 1);

        path.add("-" + nums[index]);
        int negative = solveForRemember(nums, target, sum - nums[index], index + 1);
        path.remove(path.size() - 1);
        return positive + negative;
    }

    //4.通过动态规划
    public static int findWay(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (target > sum) {
            return 0;
        }
        if ((sum + target) % 2 == 1) {
            return 0;
        }
        return solve(nums, (sum + target) / 2);

    }

    private static int solve(int[] nums, int avg) {

        int[] dp = new int[avg + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = avg; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[avg];
    }

    public static void main(String[] args) {
//        solve(new int[]{1, 1, 1, 1, 1}, 3, 0, 0);
//        solveFor(new int[]{1, 3, 4, 1, 1}, 8, 0, 0);
        System.out.println(solveForRemember(new int[]{1, 3, 4, 1, 1}, 8, 0, 0));
        System.out.println(findWay(new int[]{1, 3, 4, 1, 1}, 8));
    }
}
